<!DOCTYPE html>



  


<html class="theme-next gemini use-motion" lang="en">
<head>
  <meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>
<meta name="theme-color" content="#222">









<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />

<link href="/css/main.css?v=5.1.4" rel="stylesheet" type="text/css" />


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png?v=5.1.4">


  <link rel="mask-icon" href="/images/logo.svg?v=5.1.4" color="#222">





  <meta name="keywords" content="algorithm," />










<meta name="description" content="序:二叉树作为树的一种，是一种重要的数据结构,常见的二叉树有:满二叉树:除叶子结点外,所有结点都有两个结点,叶子结点的left,right为NULL.哈夫曼树：又称为最优二叉数，是一种带权路径最短的树。哈夫曼编码就是哈夫曼树的应用,可以用来进行编码压缩.哈夫曼树的构造见哈夫曼树的构造完全二叉树:除了最底层的叶子结点之外,其余层全满,而且叶子层集中在左端.堆是一种特殊的完全二叉树(全满或者差一个结点">
<meta property="og:type" content="article">
<meta property="og:title" content="二叉树">
<meta property="og:url" content="http://yoursite.com/2020/07/16/%E4%BA%8C%E5%8F%89%E6%A0%91/index.html">
<meta property="og:site_name" content="LinRaise&#39;s Blog">
<meta property="og:description" content="序:二叉树作为树的一种，是一种重要的数据结构,常见的二叉树有:满二叉树:除叶子结点外,所有结点都有两个结点,叶子结点的left,right为NULL.哈夫曼树：又称为最优二叉数，是一种带权路径最短的树。哈夫曼编码就是哈夫曼树的应用,可以用来进行编码压缩.哈夫曼树的构造见哈夫曼树的构造完全二叉树:除了最底层的叶子结点之外,其余层全满,而且叶子层集中在左端.堆是一种特殊的完全二叉树(全满或者差一个结点">
<meta property="og:locale" content="en_US">
<meta property="article:published_time" content="2020-07-16T12:43:58.000Z">
<meta property="article:modified_time" content="2020-07-16T12:43:58.000Z">
<meta property="article:author" content="LinRaise">
<meta property="article:tag" content="algorithm">
<meta name="twitter:card" content="summary">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Gemini',
    version: '5.1.4',
    sidebar: {"position":"right","display":"post","offset":12,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: 'Author'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://yoursite.com/2020/07/16/二叉树/"/>





  <title>二叉树 | LinRaise's Blog</title>
  








<meta name="generator" content="Hexo 4.2.1"></head>

<body itemscope itemtype="http://schema.org/WebPage" lang="en">

  
  
    
  

  <div class="container sidebar-position-right page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/"  class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">LinRaise's Blog</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle"></p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-question-circle"></i> <br />
            
            Home
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-question-circle"></i> <br />
            
            About
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-question-circle"></i> <br />
            
            Tags
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-question-circle"></i> <br />
            
            Categories
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-question-circle"></i> <br />
            
            Archives
          </a>
        </li>
      

      
        <li class="menu-item menu-item-search">
          
            <a href="javascript:;" class="popup-trigger">
          
            
              <i class="menu-item-icon fa fa-search fa-fw"></i> <br />
            
            Search
          </a>
        </li>
      
    </ul>
  

  
    <div class="site-search">
      
  <div class="popup search-popup local-search-popup">
  <div class="local-search-header clearfix">
    <span class="search-icon">
      <i class="fa fa-search"></i>
    </span>
    <span class="popup-btn-close">
      <i class="fa fa-times-circle"></i>
    </span>
    <div class="local-search-input-wrapper">
      <input autocomplete="off"
             placeholder="Searching..." spellcheck="false"
             type="text" id="local-search-input">
    </div>
  </div>
  <div id="local-search-result"></div>
</div>



    </div>
  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2020/07/16/%E4%BA%8C%E5%8F%89%E6%A0%91/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="LinRaise">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="LinRaise's Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">二叉树</h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">Posted on</span>
              
              <time title="Post created" itemprop="dateCreated datePublished" datetime="2020-07-16T12:43:58+00:00">
                2020-07-16
              </time>
            

            
              <span class="post-meta-divider">|</span>
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-check-o"></i>
              </span>
              
                <span class="post-meta-item-text">Post modified&#58;</span>
              
              <time title="Post modified" itemprop="dateModified" datetime="2020-07-16T12:43:58+00:00">
                2020-07-16
              </time>
            
          </span>

          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <p>序:二叉树作为树的一种，是一种重要的数据结构,常见的二叉树有:<br>满二叉树:除叶子结点外,所有结点都有两个结点,叶子结点的left,right为NULL.<br>哈夫曼树：又称为最优二叉数，是一种带权路径最短的树。哈夫曼编码就是哈夫曼树的应用,可以用来进行编码压缩.哈夫曼树的构造见哈夫曼树的构造<br>完全二叉树:除了最底层的叶子结点之外,其余层全满,而且叶子层集中在左端.堆是一种特殊的完全二叉树(全满或者差一个结点就全满)<br>平衡二叉树：所谓平衡二叉树指的是，左右两个子树的高度差的绝对值不超过 1。包括AVL树,红黑树.<br>红黑树：具体见红黑树问题<br>下面是我总结的这几天看过的一些常见二叉树问题.</p>
<p>1.二叉搜索树的迭代构造<br>二叉搜索树是一棵排好序的树,当新插入一个节点的时候,小于当前根结点左走,大于当前根结点右走,直至走到NULL点,就是该结点的位置.</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line">void IterativeInsert(Tree* T,node* z)&#x2F;&#x2F;插入节点  </span><br><span class="line">&#123;  </span><br><span class="line">    node* y&#x3D;NULL;  </span><br><span class="line">    node* x&#x3D;T-&gt;root;&#x2F;&#x2F;管理两个指针，父指针y,y的子树指针x  </span><br><span class="line">    while(x!&#x3D;NULL)&#x2F;&#x2F;一直向下遍历到z应该插入的位置  </span><br><span class="line">    &#123;  </span><br><span class="line">        y&#x3D;x;  </span><br><span class="line">        if(x-&gt;value &lt; z-&gt;value)  </span><br><span class="line">            x&#x3D;x-&gt;right;  </span><br><span class="line">        else x&#x3D;x-&gt;left;  </span><br><span class="line">    &#125;  </span><br><span class="line">    z-&gt;p&#x3D;y;&#x2F;&#x2F;先将z的父指针p指向y  </span><br><span class="line">    if(y&#x3D;&#x3D;NULL)&#x2F;&#x2F;若树为空，树根即为z  </span><br><span class="line">        T-&gt;root&#x3D;z;  </span><br><span class="line">    else if(z-&gt;value &lt; y-&gt;value)&#x2F;&#x2F;否则分插入左边还是右边  </span><br><span class="line">        y-&gt;left&#x3D;z;  </span><br><span class="line">    else y-&gt;right&#x3D;z;  </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<p>2.二叉搜索树的递归构造<br>1.若是空树,则插入至根结点位置</p>
<p>2.若比当前根点,插入左边.</p>
<p>3.否则插入右边</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">node* TreeInsert(node* root,node* z)</span><br><span class="line">&#123;</span><br><span class="line">	if(!root)</span><br><span class="line">		root&#x3D;z;</span><br><span class="line">	else if(root-&gt;value &lt; z-&gt;value)</span><br><span class="line">		root-&gt;right&#x3D;TreeInsert(root-&gt;right,z);</span><br><span class="line">	else root-&gt;left&#x3D;TreeInsert(root-&gt;left,z);</span><br><span class="line">	return root;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>3.二叉树三种递归遍历方式.</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line">void InorderTreeWalk(node* root)</span><br><span class="line">&#123;</span><br><span class="line">	if(!root ) return ;</span><br><span class="line">	InorderTreeWalk(root-&gt;left);</span><br><span class="line">	cout&lt;&lt;root-&gt;value&lt;&lt;&#39; &#39;;</span><br><span class="line">	InorderTreeWalk(root-&gt;right);</span><br><span class="line">&#125;</span><br><span class="line">void PriorTreeWalk(node* root)</span><br><span class="line">&#123;</span><br><span class="line">	if(!root ) return ;</span><br><span class="line">	cout&lt;&lt;root-&gt;value&lt;&lt;&#39; &#39;;</span><br><span class="line">	PriorTreeWalk(root-&gt;left);</span><br><span class="line">	PriorTreeWalk(root-&gt;right);</span><br><span class="line">&#125;</span><br><span class="line">void PostTreeWalk(node* root)</span><br><span class="line">&#123;</span><br><span class="line">	if(!root ) return ;</span><br><span class="line">	PostTreeWalk(root-&gt;left);</span><br><span class="line">	PostTreeWalk(root-&gt;right);</span><br><span class="line">	cout&lt;&lt;root-&gt;value&lt;&lt;&#39; &#39;;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>4.二叉树三种迭代遍历方式.<br>深度优先原则,输出顺序是’左子树优先’</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br></pre></td><td class="code"><pre><span class="line">void IterativeInorderWalk(node *root)&#x2F;&#x2F;迭代中序遍历  </span><br><span class="line">&#123;  </span><br><span class="line">    node* p&#x3D;root;  </span><br><span class="line">    stack&lt;node*&gt; st;&#x2F;&#x2F;利用栈  </span><br><span class="line">    if(!p)  &#x2F;&#x2F;if(!p)&#x3D;if(p&#x3D;&#x3D;null)</span><br><span class="line">        return ;  </span><br><span class="line">    while(p || !st.empty())&#x2F;&#x2F;当p不为空 或者st不为空  </span><br><span class="line">    &#123;  </span><br><span class="line">        while(p)&#x2F;&#x2F;沿着左孩子方向走到最左下。同时压栈  </span><br><span class="line">        &#123;  </span><br><span class="line">            st.push(p);  </span><br><span class="line">            p&#x3D;p-&gt;left;  </span><br><span class="line">        &#125;  </span><br><span class="line">        p&#x3D;st.top();&#x2F;&#x2F;获取栈顶元素  </span><br><span class="line">        cout&lt;&lt;p-&gt;value&lt;&lt;&quot; &quot;;  </span><br><span class="line">        st.pop();  </span><br><span class="line">        p&#x3D;p-&gt;right;  </span><br><span class="line">    &#125;  </span><br><span class="line">&#125;  </span><br><span class="line"></span><br><span class="line">void IterativePriorTreeWalk(node* root)&#x2F;&#x2F;迭代先序遍历  </span><br><span class="line">&#123;  </span><br><span class="line">    node* p&#x3D;root;  </span><br><span class="line">    stack&lt;node* &gt; st;  </span><br><span class="line">    if(!p)   </span><br><span class="line">        return ;  </span><br><span class="line">    while(p || !st.empty())  </span><br><span class="line">    &#123;  </span><br><span class="line">        while(p)  </span><br><span class="line">        &#123;  </span><br><span class="line">            cout&lt;&lt;p-&gt;value&lt;&lt;&quot; &quot;;  </span><br><span class="line">            st.push(p);  </span><br><span class="line">            p&#x3D;p-&gt;left;  </span><br><span class="line">        &#125;  </span><br><span class="line">        p&#x3D;st.top();  </span><br><span class="line">        st.pop();  </span><br><span class="line">        p&#x3D;p-&gt;right;  </span><br><span class="line">    &#125;  </span><br><span class="line">&#125;  </span><br><span class="line"></span><br><span class="line">void IterativePostWalk(node* root)  </span><br><span class="line">&#123;  </span><br><span class="line">    node* p&#x3D;root;  </span><br><span class="line">    stack&lt;node* &gt; st;  </span><br><span class="line">    node* pre&#x3D;NULL;&#x2F;&#x2F;pre表示最近一次访问的结点  </span><br><span class="line">    if(!p) return ;  </span><br><span class="line">    while(p || !st.empty())  </span><br><span class="line">    &#123;  </span><br><span class="line">        while(p)    &#x2F;&#x2F;沿着左孩子方向走到最左下  </span><br><span class="line">        &#123;  </span><br><span class="line">            st.push(p);  </span><br><span class="line">            p&#x3D;p-&gt;left;  </span><br><span class="line">        &#125;  </span><br><span class="line">        p&#x3D;st.top(); &#x2F;&#x2F;获取栈顶元素  </span><br><span class="line">        if( !p-&gt;right || p-&gt;right &#x3D;&#x3D;pre)&#x2F;&#x2F;如果p没有右孩子或者其右孩子刚刚被访问过.小窍门if (!p)表示如果p为空  </span><br><span class="line">        &#123;  </span><br><span class="line">            st.pop();  </span><br><span class="line">            cout&lt;&lt;p-&gt;value&lt;&lt;&#39; &#39;;  </span><br><span class="line">            pre&#x3D;p;      &#x2F;&#x2F;最近一次访问的节点是p  </span><br><span class="line">            p&#x3D;NULL;     &#x2F;&#x2F;使下一次循环不再执行p节点以下的压栈操作  </span><br><span class="line">        &#125;  </span><br><span class="line">        else  </span><br><span class="line">            p&#x3D;p-&gt;right;  </span><br><span class="line">    &#125;  </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>5.怎样从根结点开始逐层打印二叉树结点数据.<br>广度优先原则,需要用到队列,当访问一个当前节点CurrentNode的时候,将该结点出队,同时将该CurrentNode的左右子结点入队,重复这个操作,直至队列为空.步骤:1初始化队列.2重复出队入队操作直至队列为空.</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F;从顶部开始逐层打印二叉树结点数据,即广度遍历二叉树，需要用到队列</span><br><span class="line">void printHori(node* root)</span><br><span class="line">&#123;</span><br><span class="line">	if(!root) return ;</span><br><span class="line">	queue&lt;node*&gt; Q;</span><br><span class="line">	Q.push(root);</span><br><span class="line">	while(!Q.empty())</span><br><span class="line">	&#123;</span><br><span class="line">		node* Front&#x3D;Q.front();</span><br><span class="line">		Q.pop();</span><br><span class="line">		cout&lt;&lt;Front-&gt;value&lt;&lt;&#39; &#39;;</span><br><span class="line">		if(Front-&gt;left)</span><br><span class="line">			Q.push(Front-&gt;left);</span><br><span class="line">		if(Front-&gt;right)</span><br><span class="line">			Q.push(Front-&gt;right);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>6.获得树的深度<br>树的深度=max(左子树深度,右子树深度)+1</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F;获得树的深度</span><br><span class="line">int GetTreeDepth(node* root)</span><br><span class="line">&#123;</span><br><span class="line">	if(!root)</span><br><span class="line">		return 0;</span><br><span class="line">	int left&#x3D;GetTreeDepth(root-&gt;left);</span><br><span class="line">	int right&#x3D;GetTreeDepth(root-&gt;right);</span><br><span class="line">	return 1+(left &gt; right? left:right);&#x2F;&#x2F;max(左子树,右子树)+1为整棵树高度</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>7.如何判断一棵二叉树是否是平衡二叉树.<br>方法1:最直接的办法:获得左子树深度,获得左右子树深度,判断二者是否相差在1以内,如果是,则说明当前根结点root是平衡.否则可以判断false.继续用同样的办法判断root的左右子树是否也平衡.现在分析一下这种办法的效率:GetTreeDepth()函数类似于树的后序遍历,T(n)=2<em>T(n/2)+1,由主定理:T(n)=o(n).即,要找到树的深度需要将每个结点全扫描一遍.同样求isTreeBalance(left) 和 isTreeBalance(right)也需要将左右子树重复扫描一遍.这样重重复复扫描树的方式效率是多少?T(N)=2</em>T(N/2)+N,即T(n)=nlgn.</p>
<p>方法2:为了克服多次扫描节点方法的缺陷,我们试图用空间换时间的做法,或者是自底向上的思维方式.方法的方式是,先求根是否平衡,再求左右子树是否平衡.现在,我可以换一个角度,先求左右子树是否平衡,如果左右子树平衡,再考虑求根结点,否则直接返回false.这种方式需要在左右子树返回根时保存树的深度.即空间换时间.这种方法的复杂度为:T(n)=2*T(n/2)+1.T(n)=n.</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F;判断树是否平衡</span><br><span class="line">bool isTreeBalance(node* root)</span><br><span class="line">&#123;</span><br><span class="line">	if(!root) </span><br><span class="line">		return true ;</span><br><span class="line">	int left&#x3D;GetTreeDepth(root-&gt;left);</span><br><span class="line">	int right&#x3D;GetTreeDepth(root-&gt;right);</span><br><span class="line">	if((left - right) &gt; 1 || (right-left) &gt; 1) </span><br><span class="line">		return false;</span><br><span class="line">	return isTreeBalance(root-&gt;left) &amp;&amp; isTreeBalance(root-&gt;right);</span><br><span class="line">&#125;</span><br><span class="line">&#x2F;&#x2F;判断树是否平衡</span><br><span class="line">bool isBalanceTree(node* root,int&amp; depth)</span><br><span class="line">&#123;	</span><br><span class="line">	if(!root)</span><br><span class="line">	&#123;</span><br><span class="line">		depth&#x3D;0;</span><br><span class="line">		return true;</span><br><span class="line">	&#125;</span><br><span class="line">	int left,right;</span><br><span class="line">	if(isBalanceTree(root-&gt;left,left) &amp;&amp; isBalanceTree(root-&gt;right,right))</span><br><span class="line">	&#123;</span><br><span class="line">		if(left-right &lt;&#x3D; 1 &amp;&amp; right-left &lt;&#x3D; 1)</span><br><span class="line">		&#123;</span><br><span class="line">			depth&#x3D;1+ (left &gt; right ? left:right);</span><br><span class="line">			return true;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	return false;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<p>拓展：判断一棵树是否平衡<br><a href="http://hawstein.com/posts/4.1.html" target="_blank" rel="noopener">http://hawstein.com/posts/4.1.html</a><br>实现一个函数检查一棵树是否平衡。对于这个问题而言， 平衡指的是这棵树任意两个叶子结点到根结点的距离之差不大于1。<br>对于这道题，要审清题意。它并不是让你判断一棵树是否为平衡二叉树。 </p>
<p>平衡二叉树的定义为：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。 </p>
<p>而本题的平衡指的是这棵树任意两个叶子结点到根结点的距离之差不大于1。 这两个概念是不一样的。例如下图，</p>
<p>它是一棵平衡二叉树，但不满足本题的平衡条件。 (叶子结点f和l到根结点的距离之差等于2，不满足题目条件)</p>
<p>对于本题，只需要求出离根结点最近和最远的叶子结点， 然后看它们到根结点的距离之差是否大于1即可。</p>
<p>假设只考虑二叉树，我们可以通过遍历一遍二叉树求出每个叶子结点到根结点的距离。 使用中序遍历，依次求出从左到右的叶子结点到根结点的距离，递归实现。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;*判断树是否平衡，并不是判断是否是平衡二叉树*&#x2F;</span><br><span class="line">int Max&#x3D;INT_MIN,Min&#x3D;INT_MAX,curLen&#x3D;0;</span><br><span class="line">void FindDepth(node* root)</span><br><span class="line">&#123;</span><br><span class="line">	if( root&#x3D;&#x3D;NULL) </span><br><span class="line">	&#123;</span><br><span class="line">		return ;</span><br><span class="line">	&#125;</span><br><span class="line">	++curLen;</span><br><span class="line">	FindDepth(root-&gt;left);</span><br><span class="line">	if( root-&gt;left &#x3D;&#x3D;NULL &amp;&amp; root-&gt;right &#x3D;&#x3D;NULL)</span><br><span class="line">	&#123;</span><br><span class="line">		if( curLen &gt; Max )</span><br><span class="line">			Max&#x3D;curLen;</span><br><span class="line">		else if( curLen &lt; Min )</span><br><span class="line">			Min&#x3D;curLen;</span><br><span class="line">	&#125;</span><br><span class="line">	FindDepth(root-&gt;right);</span><br><span class="line">	--curLen;</span><br><span class="line">&#125;</span><br><span class="line">bool isBalance(node* root)</span><br><span class="line">&#123;</span><br><span class="line">	FindDepth(root);</span><br><span class="line">	return ((Max-Min)&lt;&#x3D;1);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>8.求二叉树的最低公共祖先LCA<br>性质:如果两条链有公共祖先,那么公共祖先往上的结点都重合.因为如果x=x’,那么x-&gt;next=x’-&gt;next必然成立.</p>
<p>可能性一:若是二叉搜索树.</p>
<p>1如果x,y小于root,则在左边找</p>
<p>2如果x,y大于root,则在右边找</p>
<p>3如果x,y在root之间,则root就是LCA</p>
<p>可能性二:不是二叉搜索树,甚至不是二叉树,但是,每个一节点都有parent指针</p>
<p>那么解法有2:</p>
<p>1:空间换时间:从x,y到root的链表可以保存在栈中,找出最后一个相同结点即可.</p>
<p>2.不用空间换时间,多重扫描法,x,y到root两条链路可能一长一短,相差为n个结点,那么长链表先前移n步,然后,二者同步前移,找到第一个相同结点即可.(树不含环,这种办法有效.)</p>
<p>可能性三:这是一棵只有left和right的平凡二叉树.</p>
<p>那么需要辅助空间,空间换时间法,先调用16.中的GetNodePath()获得两条从root-&gt;x和root-&gt;y的链表路径.然后比较两条链表,找到最后一个相同的结点即可.</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F;若是二叉搜索树,返回x和y的公共最低祖先LCA</span><br><span class="line">node* LowestCommonAncestor1(node* root,node* x,node* y)</span><br><span class="line">&#123;</span><br><span class="line">	if(!root || !x || !y) return NULL;</span><br><span class="line">	if(x-&gt;value &lt; root-&gt;value &amp;&amp; y-&gt;value &lt; root-&gt;value)</span><br><span class="line">		return LowestCommonAncestor1(root-&gt;left,x,y);</span><br><span class="line">	else if(x-&gt;value &gt; root-&gt;value &amp;&amp; y-&gt;value &gt; root-&gt;value)</span><br><span class="line">		return LowestCommonAncestor1(root-&gt;right,x,y);</span><br><span class="line">	else </span><br><span class="line">		return root;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F;若不是搜索二叉树,但是,每个结点都有父结点,空间换时间法,否则需要重重复复地扫描路径</span><br><span class="line">node* LowestCommonAncestor2(node* x,node* y)</span><br><span class="line">&#123;</span><br><span class="line">	stack&lt;node*&gt; st1,st2;</span><br><span class="line">	while(x)</span><br><span class="line">	&#123;</span><br><span class="line">		st1.push(x);</span><br><span class="line">		x&#x3D;x-&gt;p;</span><br><span class="line">	&#125;</span><br><span class="line">	while(y)</span><br><span class="line">	&#123;</span><br><span class="line">		st2.push(y);</span><br><span class="line">		y&#x3D;y-&gt;p;</span><br><span class="line">	&#125;</span><br><span class="line">	node* pLCA&#x3D;NULL;</span><br><span class="line">	while(!st1.empty() &amp;&amp; !st2.empty() &amp;&amp; st1.top()&#x3D;&#x3D;st2.top())</span><br><span class="line">	&#123;</span><br><span class="line">		pLCA&#x3D;st1.top();</span><br><span class="line">		st1.pop();</span><br><span class="line">		st2.pop();</span><br><span class="line">	&#125;	</span><br><span class="line">	return pLCA;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F;不用空间换时间法</span><br><span class="line">int GetListLength(node* x)</span><br><span class="line">&#123;</span><br><span class="line">	int Count&#x3D;0;</span><br><span class="line">	while(x)</span><br><span class="line">	&#123;</span><br><span class="line">		++Count;</span><br><span class="line">		x&#x3D;x-&gt;p;</span><br><span class="line">	&#125;</span><br><span class="line">	return Count;</span><br><span class="line">&#125;</span><br><span class="line">int Myabs(int val)</span><br><span class="line">&#123;</span><br><span class="line">	return val &gt; 0 ? val : -val;</span><br><span class="line">&#125;</span><br><span class="line">node* LowestCommonAncestor3(node* x,node* y)</span><br><span class="line">&#123;</span><br><span class="line">	int LengthX&#x3D;GetListLength(x);</span><br><span class="line">	int LengthY&#x3D;GetListLength(y);</span><br><span class="line">	node* pLong&#x3D;x,*pShort&#x3D;y;</span><br><span class="line">	if(LengthX &lt; LengthY)</span><br><span class="line">	&#123;</span><br><span class="line">		pLong&#x3D;y;</span><br><span class="line">		pShort&#x3D;x;</span><br><span class="line">	&#125;</span><br><span class="line">	for(int i&#x3D;0;i&lt;Myabs(LengthX-LengthY);++i)</span><br><span class="line">		pLong&#x3D;pLong-&gt;p;</span><br><span class="line">	while( pLong &amp;&amp; pShort &amp;&amp; pLong !&#x3D;pShort)</span><br><span class="line">	&#123;</span><br><span class="line">		pLong&#x3D;pLong-&gt;p;</span><br><span class="line">		pShort&#x3D;pShort-&gt;p;</span><br><span class="line">	&#125;</span><br><span class="line">	if(pLong &#x3D;&#x3D; pShort)</span><br><span class="line">		return pLong;</span><br><span class="line">	return NULL;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F;既不是二叉搜索树,也不没有parent指针,只是一棵平凡的二叉树</span><br><span class="line">bool GetNodePath(node* root, node* pNode, list&lt;node*&gt;&amp; path);</span><br><span class="line">node* LowestCommonAncestor4(node* root,node* x,node* y)</span><br><span class="line">&#123;</span><br><span class="line">	list&lt;node*&gt; path1;</span><br><span class="line">	list&lt;node*&gt; path2;</span><br><span class="line">	GetNodePath(root,x,path1);</span><br><span class="line">	GetNodePath(root,y,path2);</span><br><span class="line">	node* pLCA&#x3D;NULL;</span><br><span class="line">	list&lt;node*&gt;::const_iterator it1&#x3D;path1.begin();</span><br><span class="line">	list&lt;node*&gt;::const_iterator it2&#x3D;path2.begin();</span><br><span class="line">	while(it1 !&#x3D; path1.end() &amp;&amp; it2 !&#x3D; path2.end() &amp;&amp; *it1 &#x3D;&#x3D; * it2)</span><br><span class="line">	&#123;</span><br><span class="line">		pLCA&#x3D;*it1;</span><br><span class="line">		++it1;</span><br><span class="line">		++it2;</span><br><span class="line">	&#125;	</span><br><span class="line">	return pLCA;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>9.在二叉树中找出和为某一值的所有路径<br>要求所有路径,路径即root到某一结点的结点之集合.这是一个深度优先原则的搜索.我们很容易想到先序遍历.</p>
<p>为了跟踪路径和,我们需要一个额外的辅助栈来跟踪递归调用栈的操作过程.</p>
<p>在进入到下一个调用FindPath(left)和FindPath(right)时,递归栈会将root压入栈,因此我们也模仿进栈.当FindPath(left)和FindPath(right)返回,FindPath(root)运行周期到之后,局部函数变量root会被析造,root会从递归栈中弹出,因此,我们也从辅助栈中弹出root,只需要在中间加上判断条件,将满足条件的结果输出即可.改成迭代版也很简单.</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line">void FindPath(node* root,int expectedSum,vector&lt;int&gt;&amp; Path,int currentSum);&#x2F;&#x2F;先序遍历改装版</span><br><span class="line">void FindPath(node* root,int expectedSum)</span><br><span class="line">&#123;</span><br><span class="line">	int currentSum&#x3D;0;</span><br><span class="line">	vector&lt;int&gt; Path;</span><br><span class="line">	FindPath(root,expectedSum,Path,currentSum);</span><br><span class="line">&#125;</span><br><span class="line">void FindPath(node* root,int expectedSum,vector&lt;int&gt;&amp; Path,int currentSum)&#x2F;&#x2F;先序遍历改装版</span><br><span class="line">&#123;</span><br><span class="line">	if(!root)</span><br><span class="line">		return ;</span><br><span class="line">	&#x2F;&#x2F;访问根结点,同时将root-&gt;value加入辅助栈</span><br><span class="line">	currentSum +&#x3D; root-&gt;value;</span><br><span class="line">	Path.push_back(root-&gt;value);</span><br><span class="line">	if(root-&gt;left&#x3D;&#x3D;NULL &amp;&amp; root-&gt;right &#x3D;&#x3D;NULL &amp;&amp; currentSum &#x3D;&#x3D; expectedSum)</span><br><span class="line">	&#123;</span><br><span class="line">		for(vector&lt;int&gt;::size_type i&#x3D;0; i &lt; Path.size(); ++i)</span><br><span class="line">			cout&lt;&lt;Path[i]&lt;&lt;&#39; &#39;;</span><br><span class="line">		cout&lt;&lt;endl;</span><br><span class="line">	&#125;</span><br><span class="line">	FindPath(root-&gt;left,expectedSum,Path,currentSum);</span><br><span class="line">	FindPath(root-&gt;right,expectedSum,Path,currentSum);</span><br><span class="line">	&#x2F;&#x2F;递归栈中,此时返回时,会将父结点销毁,因为,局部函数生命周期已经到了.</span><br><span class="line">	&#x2F;&#x2F;所以辅助栈也需要和递归栈同步,将栈顶元素弹栈,同时当前路径减去栈顶元素</span><br><span class="line">	Path.pop_back();</span><br><span class="line">	currentSum-&#x3D;root-&gt;value;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>10.编写一个程序，把一个有序整数数组放到二叉树中<br>这道题做法非常多,单纯是这么要求比较奇怪,因此,我选择广度优先插入,利用队列实现,其实插成一个链表,或者随便插入不知道可不可以?没有其它要求真不知道怎么弄.</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line">node* HorizInsert(node* root,node* z)</span><br><span class="line">&#123;</span><br><span class="line">    if(!root)</span><br><span class="line">    &#123;</span><br><span class="line">        root&#x3D;z;</span><br><span class="line">        return root;</span><br><span class="line">    &#125;</span><br><span class="line">    queue&lt;node*&gt; q;</span><br><span class="line">    q.push(root);</span><br><span class="line">    while(!q.empty())</span><br><span class="line">    &#123;</span><br><span class="line">        node* Front&#x3D;q.front();</span><br><span class="line">        q.pop();</span><br><span class="line">        if(Front-&gt;left&#x3D;&#x3D;NULL)</span><br><span class="line">        &#123;</span><br><span class="line">            Front-&gt;left&#x3D;z;</span><br><span class="line">            return root;</span><br><span class="line">        &#125;</span><br><span class="line">        if(Front-&gt;right&#x3D;&#x3D;NULL)</span><br><span class="line">        &#123;</span><br><span class="line">            Front-&gt;right&#x3D;z;</span><br><span class="line">            return root;</span><br><span class="line">        &#125;</span><br><span class="line">        if(Front-&gt;left)</span><br><span class="line">            q.push(Front-&gt;left);</span><br><span class="line">        if(Front-&gt;right)</span><br><span class="line">            q.push(Front-&gt;right);</span><br><span class="line">    &#125;</span><br><span class="line">    return root;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>11.判断整数序列是不是二叉搜索树的后序遍历结果<br>典型的递归思维,后序遍历,根在最后,因此用根将二叉搜索树可以分成左右子树,再递归处理左右子树即可.</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F;判断整数序列是不是二叉搜索树的后序遍历结果  </span><br><span class="line">bool isPostTreeWalk(int* Last,int len)</span><br><span class="line">&#123;</span><br><span class="line">	if( !Last || len &lt;&#x3D; 0)</span><br><span class="line">		return false;</span><br><span class="line">	int root&#x3D;Last[len-1];</span><br><span class="line">	int i&#x3D;0;</span><br><span class="line">	while(i &lt; len-1 &amp;&amp; Last[i] &lt; root)&#x2F;&#x2F;寻找左子树划分点</span><br><span class="line">		++i;</span><br><span class="line">	for(int j&#x3D;i ; j &lt; len-1 ; ++j)</span><br><span class="line">	&#123;</span><br><span class="line">		if(Last[j] &lt; root)&#x2F;&#x2F;如果右子树中存在node&lt;root,则无法构成后序结果</span><br><span class="line">			return false;</span><br><span class="line">	&#125;</span><br><span class="line">	bool isLastTree&#x3D;true;</span><br><span class="line">	if(i &gt; 0) &#x2F;&#x2F;判断左边是不是后序树</span><br><span class="line">		isLastTree&#x3D;isPostTreeWalk(Last,i);</span><br><span class="line">	&#x2F;&#x2F;如果左边是后序树，继续判断右边，如果左边已经不是，则右边已经无需判断</span><br><span class="line">	if(isLastTree &amp;&amp; i &lt; len-1 )</span><br><span class="line">		isLastTree&#x3D;isPostTreeWalk(Last+i,len-i-1);</span><br><span class="line">	return isLastTree ;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>12.求二叉树的镜像<br>画出一个特例,我们发现只需要交换每个结点的左右指针(注意:不是数值)即可.因此在先序遍历的时候换指针即可,没有顺序要求.</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F;求二叉树的镜像  </span><br><span class="line">void MirrorRotate(node* root)</span><br><span class="line">&#123;</span><br><span class="line">	if(!root) return ;</span><br><span class="line">	swap(root-&gt;left,root-&gt;right);</span><br><span class="line">	MirrorRotate(root-&gt;right);</span><br><span class="line">	MirrorRotate(root-&gt;left);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>13.一棵排序二叉树（即二叉搜索树BST），令 f=(最大值+最小值)/2，设计一个算法，找出距离f值最近、大于f值的结点。复杂度应尽可能低。<br>BST中最大值是最右边的值,最小值是最左边的值,这样就容易求出f,再求f的父指针或者右指针都可以?(我是这么认为的).这里求父指针.</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F;找出距离f值最近、大于f值的结点。</span><br><span class="line">node* FinClearF(node* root)</span><br><span class="line">&#123;</span><br><span class="line">	if(!root) return NULL;</span><br><span class="line">	node* max,*min;</span><br><span class="line">	max&#x3D;min&#x3D;root;</span><br><span class="line">	while(min-&gt;left)</span><br><span class="line">		min&#x3D;min-&gt;left;</span><br><span class="line">	while(max-&gt;right)</span><br><span class="line">		max&#x3D;max-&gt;right;</span><br><span class="line">	int F&#x3D;(min-&gt;value + max-&gt;value) &gt;&gt; 1 ;</span><br><span class="line">	while(1)</span><br><span class="line">	&#123;</span><br><span class="line">		if(root-&gt;value &lt;&#x3D; F)</span><br><span class="line">			root&#x3D;root-&gt;right;</span><br><span class="line">		else</span><br><span class="line">		&#123;</span><br><span class="line">			return root;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<p>14.把二叉搜索树转变成排序的双向链表<br>其实就是中序遍历的迭代版本,只是将中间的访问结点代码换成了调整指针.这种办法返回的是链表的最后一个指针LastVist,因为是双链表,这也可以接受.</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F;迭代法</span><br><span class="line">node* iTreeToList(node* root)</span><br><span class="line">&#123;</span><br><span class="line">	node* p&#x3D;root;</span><br><span class="line">	stack&lt;node*&gt; st;</span><br><span class="line">	node* LastVist&#x3D;NULL;</span><br><span class="line">	while(p || !st.empty())</span><br><span class="line">	&#123;</span><br><span class="line">		while(p)</span><br><span class="line">		&#123;</span><br><span class="line">			st.push(p);</span><br><span class="line">			p&#x3D;p-&gt;left;</span><br><span class="line">		&#125;</span><br><span class="line">		p&#x3D;st.top();</span><br><span class="line">		st.pop();</span><br><span class="line">		&#x2F;&#x2F;cout&lt;&lt;p-&gt;value&lt;&lt;&#39; &#39;;</span><br><span class="line">		if(LastVist)</span><br><span class="line">		&#123;</span><br><span class="line">			LastVist-&gt;right&#x3D;p;</span><br><span class="line">			p-&gt;left&#x3D;LastVist;</span><br><span class="line">		&#125;</span><br><span class="line">		LastVist&#x3D;p;</span><br><span class="line">		p&#x3D;p-&gt;right;</span><br><span class="line">	&#125;</span><br><span class="line">	return LastVist;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>15.打印二叉树中的所有路径.<br>和前边的思路类似,用辅助栈记录递归栈的运行过程,先序遍历(深搜)的过程中,遇到叶子结点(!left &amp;&amp; !right的结点)就输出辅助栈的内容.</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F;输出二叉树的所有路径</span><br><span class="line">void OutputTreePath(node* root,list&lt;node*&gt;&amp; path)</span><br><span class="line">&#123;</span><br><span class="line">	if(!root) return ; </span><br><span class="line">	path.push_back(root);</span><br><span class="line">	if(!root-&gt;left &amp;&amp; !root-&gt;right)</span><br><span class="line">	&#123;</span><br><span class="line">		for(list&lt;node*&gt;::const_iterator it&#x3D;path.begin();it !&#x3D;path.end();++it)</span><br><span class="line">			cout&lt;&lt;(*it)-&gt;value&lt;&lt;&#39; &#39;;</span><br><span class="line">		cout&lt;&lt;endl;</span><br><span class="line">	&#125;</span><br><span class="line">	OutputTreePath(root-&gt;left,path);</span><br><span class="line">	OutputTreePath(root-&gt;right,path);</span><br><span class="line">	&#x2F;&#x2F;运行到这里的时候,函数生命周期到,在返回上一层时</span><br><span class="line">	&#x2F;&#x2F;局部函数会析构root(当前根结点),对应地,也应该将root从path中的值弹出</span><br><span class="line">	path.pop_back();</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>16.求二叉树中从根到某一结点的一条路径.<br>思路一如既往还是利用辅助栈来追踪递归调用栈的运行过程,只是过程有所区别,将结点入栈,如果在结点的左边能找到一条路径,那么不需要和递归栈同步(即弹栈),直接返回true,如果左边没找到这样的一条路径,再到右边找,如果找到了,返回true.如果左右都找不到存在一条这样的路径,则说明在这个结点上不可能存在这样的路径,需要在辅助栈中弹出这个结点.再遍历其它结点.实质上也是先序遍历的改装版.</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F;获得二叉树中从根到某一结点的一条路径</span><br><span class="line">bool GetNodePath(node* root, node* pNode, list&lt;node*&gt;&amp; path)</span><br><span class="line">&#123;</span><br><span class="line">	if(root &#x3D;&#x3D; pNode)&#x2F;&#x2F;如果root&#x3D;&#x3D;nNode,Done</span><br><span class="line">	&#123;</span><br><span class="line">		path.push_back(pNode);</span><br><span class="line">		return true;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	path.push_back(root);&#x2F;&#x2F;1用root实始化容器</span><br><span class="line">	 </span><br><span class="line">	bool isFound &#x3D; false;</span><br><span class="line">	if(root-&gt;left)</span><br><span class="line">		isFound &#x3D; GetNodePath(root-&gt;left, pNode, path);</span><br><span class="line">	if(!isFound &amp;&amp; root-&gt;right)</span><br><span class="line">		isFound &#x3D; GetNodePath(root-&gt;right, pNode, path);</span><br><span class="line">	 </span><br><span class="line">	if(!isFound)&#x2F;&#x2F;如果1中的左右子树都没找到，说明在这个root上不存在这样的路径，需要将root弹出</span><br><span class="line">		path.pop_back();</span><br><span class="line">	 </span><br><span class="line">	return isFound;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>17判断B子树是否是A子树的子结构<br>这个似乎是有问题的,暂时还没有找到好的解决方案.求大神相助.</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F;判断B是否是A的子结构</span><br><span class="line">bool isAcontainB(node* rootA,node* rootB)</span><br><span class="line">&#123;</span><br><span class="line">	if(!rootB)</span><br><span class="line">		return true;</span><br><span class="line">	if(!rootA)</span><br><span class="line">		return false;</span><br><span class="line">	if(rootA-&gt;value &#x3D;&#x3D; rootB-&gt;value)</span><br><span class="line">		return isAcontainB(rootA-&gt;left,rootB-&gt;left) &amp;&amp; isAcontainB(rootA-&gt;right,rootB-&gt;right);</span><br><span class="line">	return isAcontainB(rootA-&gt;left,rootB) || isAcontainB(rootA-&gt;right,rootB);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>18.利用先序和中序结果重建二叉树<br>在先序中找到根,利用根在中序中找到划分位置,再从划分位置把先序切成两部分,再依次递归即可.</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F;利用先序和中序结果重建二叉树</span><br><span class="line">node* RebuildTree(int* Prec,int * Post,int n)</span><br><span class="line">&#123;</span><br><span class="line">	if(!Prec || !Post || n&lt;1) </span><br><span class="line">		return NULL;</span><br><span class="line">	node* root&#x3D;new node(Prec[0]);</span><br><span class="line">	int i;</span><br><span class="line">	for(i&#x3D;0 ; i&lt;n &amp;&amp; Post[i] !&#x3D;Prec[0] ; ++i );</span><br><span class="line">	</span><br><span class="line"></span><br><span class="line">	root-&gt;left&#x3D;RebuildTree(Prec+1,Post,i);</span><br><span class="line">	</span><br><span class="line">	root-&gt;right&#x3D;RebuildTree(Prec+1+i,Post+1+i,n-i-1);</span><br><span class="line">	return root;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<p>19.求二叉树中叶子结点的个数</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">void CountLeaves(node* root,int&amp; Count)</span><br><span class="line">&#123;</span><br><span class="line">	if(!root ) return ;</span><br><span class="line">	if(!root-&gt;left &amp;&amp; !root-&gt;right)</span><br><span class="line">		++Count;</span><br><span class="line">	CountLeaves(root-&gt;left,Count);</span><br><span class="line">	CountLeaves(root-&gt;right,Count);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<p>20.求二叉树中节点的最大距离。<br>如果我们把二叉树看成一个图，父子节点之间的连线是双向的，我们定义距离为两个节点之间边的个数。（来自编程之美）</p>
<p>特点：相距最远的两个节点，一定是两个叶子节点，或者一个结点到它的根节点。（为什么？）因为如果当前结点不是叶子结点，即它还有子结点，那么它的子结点到另一个端点的距离肯定可以达到更远。如果是根结点，那么根结点只可能有一条支路。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F; 数据结构定义</span><br><span class="line">struct NODE</span><br><span class="line">&#123;</span><br><span class="line">     NODE* pLeft;        	&#x2F;&#x2F; 左子树</span><br><span class="line">     NODE* pRight;      	&#x2F;&#x2F; 右子树</span><br><span class="line">     int nMaxLeft;      	&#x2F;&#x2F; 左子树中的最长距离</span><br><span class="line">     int nMaxRight;     	&#x2F;&#x2F; 右子树中的最长距离</span><br><span class="line">     char chValue;    	&#x2F;&#x2F; 该节点的值</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line">int nMaxLen &#x3D; 0;</span><br><span class="line"></span><br><span class="line">&#x2F;&#x2F; 寻找树中最长的两段距离</span><br><span class="line">void FindMaxLen(NODE* pRoot)</span><br><span class="line">&#123;</span><br><span class="line">     &#x2F;&#x2F; 遍历到叶子节点，返回</span><br><span class="line">     if(pRoot &#x3D;&#x3D; NULL)</span><br><span class="line">     &#123;</span><br><span class="line">          return;</span><br><span class="line">     &#125;</span><br><span class="line"></span><br><span class="line">     &#x2F;&#x2F; 如果左子树为空，那么该节点的左边最长距离为0</span><br><span class="line">     if(pRoot -&gt; pLeft &#x3D;&#x3D; NULL)</span><br><span class="line">     &#123;</span><br><span class="line">          pRoot -&gt; nMaxLeft &#x3D; 0; </span><br><span class="line">     &#125;</span><br><span class="line">     </span><br><span class="line">     &#x2F;&#x2F; 如果右子树为空，那么该节点的右边最长距离为0</span><br><span class="line">     if(pRoot -&gt; pRight &#x3D;&#x3D; NULL)</span><br><span class="line">     &#123;</span><br><span class="line">          pRoot -&gt; nMaxRight &#x3D; 0;</span><br><span class="line">     &#125;</span><br><span class="line">     </span><br><span class="line">     &#x2F;&#x2F; 如果左子树不为空，递归寻找左子树最长距离</span><br><span class="line">     if(pRoot -&gt; pLeft !&#x3D; NULL)</span><br><span class="line">     &#123;</span><br><span class="line">          FindMaxLen(pRoot -&gt; pLeft);</span><br><span class="line">     &#125;</span><br><span class="line">     </span><br><span class="line">     &#x2F;&#x2F; 如果右子树不为空，递归寻找右子树最长距离</span><br><span class="line">     if(pRoot -&gt; pRight !&#x3D; NULL)</span><br><span class="line">     &#123;</span><br><span class="line">          FindMaxLen(pRoot -&gt; pRight);</span><br><span class="line">     &#125;</span><br><span class="line">     </span><br><span class="line">     &#x2F;&#x2F; 计算左子树最长节点距离</span><br><span class="line">     if(pRoot -&gt; pLeft !&#x3D; NULL)</span><br><span class="line">     &#123;</span><br><span class="line">          int nTempMax &#x3D; 0;</span><br><span class="line">          if(pRoot -&gt; pLeft -&gt; nMaxLeft &gt; pRoot -&gt; pLeft -&gt; nMaxRight)</span><br><span class="line">          &#123;</span><br><span class="line">               nTempMax &#x3D; pRoot -&gt; pLeft -&gt; nMaxLeft;</span><br><span class="line">          &#125;</span><br><span class="line">          else</span><br><span class="line">          &#123;</span><br><span class="line">               nTempMax &#x3D; pRoot -&gt; pLeft -&gt; nMaxRight;</span><br><span class="line">          &#125;</span><br><span class="line">          pRoot -&gt; nMaxLeft &#x3D; nTempMax + 1;</span><br><span class="line">     &#125;</span><br><span class="line">     </span><br><span class="line">     &#x2F;&#x2F; 计算右子树最长节点距离</span><br><span class="line">     if(pRoot -&gt; pRight !&#x3D; NULL)</span><br><span class="line">     &#123;</span><br><span class="line">          int nTempMax &#x3D; 0;</span><br><span class="line">          if(pRoot -&gt; pRight -&gt; nMaxLeft &gt; pRoot -&gt; pRight -&gt; nMaxRight)</span><br><span class="line">          &#123;</span><br><span class="line">               nTempMax &#x3D; pRoot -&gt; pRight -&gt; nMaxLeft;</span><br><span class="line">          &#125;</span><br><span class="line">          else</span><br><span class="line">          &#123;</span><br><span class="line">               nTempMax &#x3D; pRoot -&gt; pRight -&gt; nMaxRight;</span><br><span class="line">          &#125;</span><br><span class="line">          pRoot -&gt; nMaxRight &#x3D; nTempMax + 1;</span><br><span class="line">     &#125;</span><br><span class="line">     </span><br><span class="line">     &#x2F;&#x2F; 更新最长距离</span><br><span class="line">     if(pRoot -&gt; nMaxLeft + pRoot -&gt; nMaxRight &gt; nMaxLen)</span><br><span class="line">     &#123;</span><br><span class="line">          nMaxLen &#x3D; pRoot -&gt; nMaxLeft + pRoot -&gt; nMaxRight;</span><br><span class="line">     &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>递归总结：</p>
<p>1.先弄清楚递归的顺序。在递归的过程中，往往需要假设后续的调用已经完成，在此基础之上，才实现递归的逻辑。</p>
<p>2.分析清楚递归体的逻辑，然后写出来。</p>
<p>3.考虑清楚递归退出的边界条件。即在哪些地方写上return.</p>
<p>21.打印二叉树中某层的结点。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F; 输出以root为根节点中的第level层中的所有节点（从左到右）, 成功返回1，</span><br><span class="line">&#x2F;&#x2F; 失败则返回0</span><br><span class="line">&#x2F;&#x2F; @param</span><br><span class="line">&#x2F;&#x2F; root 为二叉树的根节点 </span><br><span class="line">&#x2F;&#x2F; level为层次数，其中根节点为第0层</span><br><span class="line">int PrintNodeAtLevel(Node* root, int level)</span><br><span class="line">&#123;</span><br><span class="line">     if(!root || level &lt; 0)</span><br><span class="line">          return 0;</span><br><span class="line">     if(level &#x3D;&#x3D; 0)</span><br><span class="line">     &#123;</span><br><span class="line">          cout &lt;&lt; root -&gt; data &lt;&lt; &quot; &quot;;</span><br><span class="line">          return 1;</span><br><span class="line">     &#125;</span><br><span class="line">     return PrintNodeAtLevel(node -&gt; lChild, level - 1) + PrintNodeAtLevel</span><br><span class="line">       (node -&gt; rChild, level - 1);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>22.判断两棵二叉树是否相等</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line">bool IsEqual(node *root1, node *root2)</span><br><span class="line">&#123;</span><br><span class="line">	if (root1 !&#x3D; NULL &amp;&amp; root2 !&#x3D; NULL)</span><br><span class="line">	&#123;</span><br><span class="line">		if (root1-&gt;data !&#x3D; root2-&gt;data)</span><br><span class="line">		&#123;</span><br><span class="line">			return false;</span><br><span class="line">		&#125;</span><br><span class="line">		if (IsEqual(root1-&gt;left, root2-&gt;left) &amp;&amp; IsEqual(root1-&gt;right, root2-&gt;right))</span><br><span class="line">		&#123;</span><br><span class="line">			return true;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	else</span><br><span class="line">	&#123;</span><br><span class="line">		if (root1 &#x3D;&#x3D; NULL &amp;&amp; root2 &#x3D;&#x3D; NULL)</span><br><span class="line">		&#123;</span><br><span class="line">			return true;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	return false;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/tags/algorithm/" rel="tag"># algorithm</a>
          
        </div>
      

      
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2020/07/16/%E8%85%BE%E8%AE%AF%E4%B8%80%E9%81%93%E9%9D%A2%E8%AF%95%E9%A2%98/" rel="next" title="腾讯一道面试题">
                <i class="fa fa-chevron-left"></i> 腾讯一道面试题
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2020/07/17/%E5%8D%A1%E7%89%B9%E5%85%B0%E6%95%B0/" rel="prev" title="卡特兰数">
                卡特兰数 <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          


          

  



        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      

      <section class="site-overview-wrap sidebar-panel sidebar-panel-active">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <p class="site-author-name" itemprop="name">LinRaise</p>
              <p class="site-description motion-element" itemprop="description"></p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">16</span>
                  <span class="site-state-item-name">posts</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/categories/index.html">
                  <span class="site-state-item-count">2</span>
                  <span class="site-state-item-name">categories</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/tags/index.html">
                  <span class="site-state-item-count">1</span>
                  <span class="site-state-item-name">tags</span>
                </a>
              </div>
            

          </nav>

          

          

          
          

          
          

          

        </div>
      </section>

      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; <span itemprop="copyrightYear">2020</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">LinRaise</span>

  
</div>


  <div class="powered-by">Powered by <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a></div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">Theme &mdash; <a class="theme-link" target="_blank" href="https://github.com/iissnan/hexo-theme-next">NexT.Gemini</a> v5.1.4</div>




        







        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.4"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.4"></script>



  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=5.1.4"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=5.1.4"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  





  












  

  <script type="text/javascript">
    // Popup Window;
    var isfetched = false;
    var isXml = true;
    // Search DB path;
    var search_path = "search.xml";
    if (search_path.length === 0) {
      search_path = "search.xml";
    } else if (/json$/i.test(search_path)) {
      isXml = false;
    }
    var path = "/" + search_path;
    // monitor main search box;

    var onPopupClose = function (e) {
      $('.popup').hide();
      $('#local-search-input').val('');
      $('.search-result-list').remove();
      $('#no-result').remove();
      $(".local-search-pop-overlay").remove();
      $('body').css('overflow', '');
    }

    function proceedsearch() {
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay"></div>')
        .css('overflow', 'hidden');
      $('.search-popup-overlay').click(onPopupClose);
      $('.popup').toggle();
      var $localSearchInput = $('#local-search-input');
      $localSearchInput.attr("autocapitalize", "none");
      $localSearchInput.attr("autocorrect", "off");
      $localSearchInput.focus();
    }

    // search function;
    var searchFunc = function(path, search_id, content_id) {
      'use strict';

      // start loading animation
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay">' +
          '<div id="search-loading-icon">' +
          '<i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>' +
          '</div>' +
          '</div>')
        .css('overflow', 'hidden');
      $("#search-loading-icon").css('margin', '20% auto 0 auto').css('text-align', 'center');

      $.ajax({
        url: path,
        dataType: isXml ? "xml" : "json",
        async: true,
        success: function(res) {
          // get the contents from search data
          isfetched = true;
          $('.popup').detach().appendTo('.header-inner');
          var datas = isXml ? $("entry", res).map(function() {
            return {
              title: $("title", this).text(),
              content: $("content",this).text(),
              url: $("url" , this).text()
            };
          }).get() : res;
          var input = document.getElementById(search_id);
          var resultContent = document.getElementById(content_id);
          var inputEventFunction = function() {
            var searchText = input.value.trim().toLowerCase();
            var keywords = searchText.split(/[\s\-]+/);
            if (keywords.length > 1) {
              keywords.push(searchText);
            }
            var resultItems = [];
            if (searchText.length > 0) {
              // perform local searching
              datas.forEach(function(data) {
                var isMatch = false;
                var hitCount = 0;
                var searchTextCount = 0;
                var title = data.title.trim();
                var titleInLowerCase = title.toLowerCase();
                var content = data.content.trim().replace(/<[^>]+>/g,"");
                var contentInLowerCase = content.toLowerCase();
                var articleUrl = decodeURIComponent(data.url);
                var indexOfTitle = [];
                var indexOfContent = [];
                // only match articles with not empty titles
                if(title != '') {
                  keywords.forEach(function(keyword) {
                    function getIndexByWord(word, text, caseSensitive) {
                      var wordLen = word.length;
                      if (wordLen === 0) {
                        return [];
                      }
                      var startPosition = 0, position = [], index = [];
                      if (!caseSensitive) {
                        text = text.toLowerCase();
                        word = word.toLowerCase();
                      }
                      while ((position = text.indexOf(word, startPosition)) > -1) {
                        index.push({position: position, word: word});
                        startPosition = position + wordLen;
                      }
                      return index;
                    }

                    indexOfTitle = indexOfTitle.concat(getIndexByWord(keyword, titleInLowerCase, false));
                    indexOfContent = indexOfContent.concat(getIndexByWord(keyword, contentInLowerCase, false));
                  });
                  if (indexOfTitle.length > 0 || indexOfContent.length > 0) {
                    isMatch = true;
                    hitCount = indexOfTitle.length + indexOfContent.length;
                  }
                }

                // show search results

                if (isMatch) {
                  // sort index by position of keyword

                  [indexOfTitle, indexOfContent].forEach(function (index) {
                    index.sort(function (itemLeft, itemRight) {
                      if (itemRight.position !== itemLeft.position) {
                        return itemRight.position - itemLeft.position;
                      } else {
                        return itemLeft.word.length - itemRight.word.length;
                      }
                    });
                  });

                  // merge hits into slices

                  function mergeIntoSlice(text, start, end, index) {
                    var item = index[index.length - 1];
                    var position = item.position;
                    var word = item.word;
                    var hits = [];
                    var searchTextCountInSlice = 0;
                    while (position + word.length <= end && index.length != 0) {
                      if (word === searchText) {
                        searchTextCountInSlice++;
                      }
                      hits.push({position: position, length: word.length});
                      var wordEnd = position + word.length;

                      // move to next position of hit

                      index.pop();
                      while (index.length != 0) {
                        item = index[index.length - 1];
                        position = item.position;
                        word = item.word;
                        if (wordEnd > position) {
                          index.pop();
                        } else {
                          break;
                        }
                      }
                    }
                    searchTextCount += searchTextCountInSlice;
                    return {
                      hits: hits,
                      start: start,
                      end: end,
                      searchTextCount: searchTextCountInSlice
                    };
                  }

                  var slicesOfTitle = [];
                  if (indexOfTitle.length != 0) {
                    slicesOfTitle.push(mergeIntoSlice(title, 0, title.length, indexOfTitle));
                  }

                  var slicesOfContent = [];
                  while (indexOfContent.length != 0) {
                    var item = indexOfContent[indexOfContent.length - 1];
                    var position = item.position;
                    var word = item.word;
                    // cut out 100 characters
                    var start = position - 20;
                    var end = position + 80;
                    if(start < 0){
                      start = 0;
                    }
                    if (end < position + word.length) {
                      end = position + word.length;
                    }
                    if(end > content.length){
                      end = content.length;
                    }
                    slicesOfContent.push(mergeIntoSlice(content, start, end, indexOfContent));
                  }

                  // sort slices in content by search text's count and hits' count

                  slicesOfContent.sort(function (sliceLeft, sliceRight) {
                    if (sliceLeft.searchTextCount !== sliceRight.searchTextCount) {
                      return sliceRight.searchTextCount - sliceLeft.searchTextCount;
                    } else if (sliceLeft.hits.length !== sliceRight.hits.length) {
                      return sliceRight.hits.length - sliceLeft.hits.length;
                    } else {
                      return sliceLeft.start - sliceRight.start;
                    }
                  });

                  // select top N slices in content

                  var upperBound = parseInt('1');
                  if (upperBound >= 0) {
                    slicesOfContent = slicesOfContent.slice(0, upperBound);
                  }

                  // highlight title and content

                  function highlightKeyword(text, slice) {
                    var result = '';
                    var prevEnd = slice.start;
                    slice.hits.forEach(function (hit) {
                      result += text.substring(prevEnd, hit.position);
                      var end = hit.position + hit.length;
                      result += '<b class="search-keyword">' + text.substring(hit.position, end) + '</b>';
                      prevEnd = end;
                    });
                    result += text.substring(prevEnd, slice.end);
                    return result;
                  }

                  var resultItem = '';

                  if (slicesOfTitle.length != 0) {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + highlightKeyword(title, slicesOfTitle[0]) + "</a>";
                  } else {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + title + "</a>";
                  }

                  slicesOfContent.forEach(function (slice) {
                    resultItem += "<a href='" + articleUrl + "'>" +
                      "<p class=\"search-result\">" + highlightKeyword(content, slice) +
                      "...</p>" + "</a>";
                  });

                  resultItem += "</li>";
                  resultItems.push({
                    item: resultItem,
                    searchTextCount: searchTextCount,
                    hitCount: hitCount,
                    id: resultItems.length
                  });
                }
              })
            };
            if (keywords.length === 1 && keywords[0] === "") {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-search fa-5x" /></div>'
            } else if (resultItems.length === 0) {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-frown-o fa-5x" /></div>'
            } else {
              resultItems.sort(function (resultLeft, resultRight) {
                if (resultLeft.searchTextCount !== resultRight.searchTextCount) {
                  return resultRight.searchTextCount - resultLeft.searchTextCount;
                } else if (resultLeft.hitCount !== resultRight.hitCount) {
                  return resultRight.hitCount - resultLeft.hitCount;
                } else {
                  return resultRight.id - resultLeft.id;
                }
              });
              var searchResultList = '<ul class=\"search-result-list\">';
              resultItems.forEach(function (result) {
                searchResultList += result.item;
              })
              searchResultList += "</ul>";
              resultContent.innerHTML = searchResultList;
            }
          }

          if ('auto' === 'auto') {
            input.addEventListener('input', inputEventFunction);
          } else {
            $('.search-icon').click(inputEventFunction);
            input.addEventListener('keypress', function (event) {
              if (event.keyCode === 13) {
                inputEventFunction();
              }
            });
          }

          // remove loading animation
          $(".local-search-pop-overlay").remove();
          $('body').css('overflow', '');

          proceedsearch();
        }
      });
    }

    // handle and trigger popup window;
    $('.popup-trigger').click(function(e) {
      e.stopPropagation();
      if (isfetched === false) {
        searchFunc(path, 'local-search-input', 'local-search-result');
      } else {
        proceedsearch();
      };
    });

    $('.popup-btn-close').click(onPopupClose);
    $('.popup').click(function(e){
      e.stopPropagation();
    });
    $(document).on('keyup', function (event) {
      var shouldDismissSearchPopup = event.which === 27 &&
        $('.search-popup').is(':visible');
      if (shouldDismissSearchPopup) {
        onPopupClose();
      }
    });
  </script>





  

  

  

  
  

  

  

  

</body>
</html>
